package com.xiayuanxing.arithmetic.DataStructures.Sort;

import java.util.Arrays;

/**
 * @program: arithmetic
 * @description: 快速排序
 * @author: xia yuan xing
 * @create: 2021-09-25 09:45
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] array = {-9,78,0,23,-567,70};

        quickSort(array,0,array.length-1);
//        quickSort1(array,0,array.length-1);
        System.out.println(Arrays.toString(array));

    }


    /**
     * 快速排序：写法一
     * @param array
     * @param low
     * @param high
     */
    public static void quickSort(int[] array,int low,int high){
        int pivot,p_pos,i,t;

        if (low<high){

            p_pos = low;
            pivot = array[p_pos];
            for (i = low +1 ; i <=high ; i++) {
                if (array[i] < pivot){
                    p_pos++;
                    t = array[p_pos];
                    array[p_pos] = array[i];
                    array[i] = t;
                }
            }
            t = array[low];
            array[low] = array[p_pos];
            array[p_pos] = t;

            quickSort(array,low,p_pos -1);
            quickSort(array,p_pos + 1,high);
        }
    }


    /**
     * 快速排序：写法二
     * @param array
     * @param left
     * @param right
     */
    public static void quickSort1(int[] array,int left,int right){

        //左下标
        int l = left;
        //右下标
        int r = right;
        // pivot 中轴值
        int pivot = array[(left + right)/2];

        //临时变量，交换时使用
        int temp;

        //循环的目的：让比中轴值小的放到左边，让比中轴值大的放到右边
        while (l < r){
            //在中轴值得左边一直找，找到一个大于或者等于中轴值得值，才退出
            while (array[l] < pivot){
                l+=1;
            }

            //在中轴值得右边一直找，找到一个小于或者等于中轴值得值，才退出
            while (array[r] > pivot){
                r -=1;
            }


            //说明中轴左右的值已经按照左边全部是小于或等于中轴值得值
            //右边全部是大于或等于中轴值得值
            if (l >= r){
                break;
            }
            //交换
            temp = array[l];
            array[l] = array[r];
            array[r] = temp;

            //若array[l] == 中轴值，那么就让array[r] -- 进行前移
            if (array[l] == pivot){
                r -= 1;
            }

            //若array[r] == 中轴值，那么就让array[l] ++ 进行后移
            if (array[r] == pivot){
                l += 1;
            }

        }

        //如果 l == r,就必须 L++,R--,否则会栈溢出
        if (l == r){
            l += 1;
            r -= 1;
        }

        //向左递归
        if (left < r){

            quickSort1(array,left,r);
        }

        //向右递归
        if (right > l){
            quickSort1(array,l,right);
        }

    }

}